var rdlist = function( ){
	var head = null;
	var tail = null;
	//插入辅助函数
	function insertFirst(node){
		node.prev = null;
		node.next = null;
		head = node;
		tail = node;
	}
	function insertHead(node){
		node.prev = null;
		node.next = head;
		head.prev = node;
		head = node;
	}
	function insertTail(node){
		node.prev = tail;
		node.next = null;
		tail.next = node;
		tail = node;
	}
	function insert(node,before,after){
		node.prev = before;
		node.next = after;
		before.next = node;
		after.prev = node;
	}
	//移除辅助函数
	function removeLast(){
		head = null;
		tail = null;
	}
	function removeHead(){
		head = head.next;
		head.prev = null;
	}
	function removeTail(){
		tail = tail.prev;
		tail.next = null;
	}
	function remove(node){
		node.prev.next = node.next;
		node.next.prev = node.prev;
	}
	
	return {
		add: function( e ){
			var present = {
				e: e,
				prev: null,
				next: null
			};
			if(head==null){
				insertFirst(present);
			}
			else{
				insertTail(present);
			}
			return {
				remove: function( ){
					if(present.prev==null){
						if(present.next==null){
							removeLast();
						}
						else{
							removeHead();
						}
					}
					else{
						if(present.next==null){
							removeTail();
						}
						else{
							remove(present);
						}
					}
					present = null;
				}
			};
		},
		foreach: function( op ){
			var present = head;
			while(present!=null){
				op(present.e);
				present = present.next;
			}
		},
		foreach_reverse: function( op ){
			var present = tail;
			while(present!=null){
				op(present.e);
				present = present.prev;
			}
		},
		sort: function( less ){
			//只有一项/空队列
			if(head==tail){
				return;
			}
			//每一个节点
			var present = head.next;
			while(present!=null){
				//向前寻找最后一个比他小的
				var target = present.prev;
				while(target!=null&&less(present.e,target.e)){
					target = target.prev;
				}
				var node = present;
				//步进
				present = present.next;
				//需要挪动
				if(target!=node.prev){
					//先移出（一定不是头）
					if(node.next==null){
						removeTail();
					}
					else{
						remove(node);
					}
					//再插入（队列不为空）
					if(target==null){
						insertHead(node);
					}
					else{
						insert(node,target,target.next);
					}
				}
			}
		}
	};
};

var println = function(str){
	document.getElementById("console").innerHTML += "<p>"+str+"</p>";
};

window.onload = function( body ){
	var DispMessages = function(dli){
		println("--------------------------------------------------------------");
		dli.foreach(function(msg){
			println("author: "+msg.author);
			println("time: "+msg.time);
			println("title: "+msg.title);
		});
		println("--------------------------------------------------------------");
		println("<br />");
	};
	
	var Message = function(id,title,author,time){
		return {
			id: id,
			title: title,
			author: author,
			time: time
		};
	};
	
	var myLi = rdlist();
	var m1 = Message(3,"first","huh1","3333");
	var m2 = Message(2,"second","huh2","2222");
	var m3 = Message(4,"third","huh3","4444");
	var m4 = Message(1,"forth","huh4","1111");
	var h1 = myLi.add(m1);
	var h2 = myLi.add(m2);
	var h3 = myLi.add(m3);
	var h4 = myLi.add(m4);
	DispMessages(myLi);
	
	myLi.sort(function(l,r){
		return l.id<r.id;
	});
	DispMessages(myLi);

	h2.remove();
	DispMessages(myLi);

	h3.remove();
	DispMessages(myLi);

	h2 = myLi.add(m2);
	DispMessages(myLi);

	myLi.sort(function(l,r){
		return l.id<r.id;
	});
	DispMessages(myLi);
	
	h1.remove();
	DispMessages(myLi);

	h2.remove();
	DispMessages(myLi);

	h4.remove();
	DispMessages(myLi);

	myLi.sort(function(l,r){
		return l.id<r.id;
	});
	DispMessages(myLi);
};
